Data may be stored locally or remotely according to a variety of storage configurations and implementations. For instance, cloud computing is a recent development related to the deployment of remote servers and software networks that provide for centralized data storage and online access to resources and services, referred to as “cloud services.” A set of cloud servers may host resources/services for a single user (a “tenant”), or for multiple related or unrelated users (a “multi-tenant” system). Similarly, data may be stored “on-site” by an entity, and may be accessed by that entity in that on-site data storage.
Data breaches are an increasing concern as more and more data is digitally stored. For example, data breaches are arguably the main deterrent for the adoption of cloud and other services for applications that manage sensitive, business critical information. On a public cloud, applications must guard against potentially malicious cloud administrators, malicious co-tenants, and other entities that can obtain access to data through various legal means. Since the compute and storage platform itself cannot be trusted, any data that appears in cleartext (data that is not encrypted) anywhere on the cloud platform (on disk, in memory, over the wire, etc.) has to be considered susceptible to leakage or malicious corruption. In vertical industries such as finance, banking, and healthcare, compliance requirements mandate strong protection against these types of threats.
Accordingly, in some cases, a database server may store encrypted data, but have no access to the encryption keys for security reasons. This guarantees that any data stored in the database is encrypted until it passes to the client application (e.g., an intermediate application managed by the client entity), which runs in a protected environment. To address handling queries to encrypted data, the database server may use homomorphic encryption schemes. Such encryption schemes allow operations to be performed directly on encrypted data without requiring encryption keys. For example, the encrypted sum of two values a and b may be computed directly from the encrypted values of a and b (E(a) and E(b)) without knowing their individual values. However, homomorphic encryption schemes are extremely expensive—performing operations on homomorphically encrypted values can be several orders of magnitude slower than operations on unencrypted data. Another set of encryption schemes known as partially homomorphic encryption (PHE) schemes permit a limited set of operations on encrypted data. These schemes are relatively fast but are restricted in the kinds of operations they permit. Due to these security requirements and encrypted data computing constraints, handling queries on databases in a secure and efficient manner is difficult to implement.